package com.algorithm;

import java.util.*;

/**
 * 重复的DNA序列
 */
public class RepeatedDnaSequences {

    public static List<String> findRepeatedDnaSequences(String s) {
//        Map<String,Integer> map=new HashMap<>();
//        int length = s.length();
//        for (int i=0;i<=length-10;i++){
//            String substring = s.substring(i, i + 10);
//            if (map.containsKey(substring)){
//                map.put(substring,map.get(substring)+1);
//            }else {
//                map.put(substring,1);
//            }
//        }
//        map.entrySet().removeIf(x->x.getValue()<=1);
//        return new ArrayList<>(map.keySet()) ;

        Set<String> set1=new HashSet<>();
        Set<String> set2=new HashSet<>();
        int length = s.length();
        for (int i=0;i<=length-10;i++){
            String substring = s.substring(i, i + 10);
            if (set1.contains(substring)){
                set2.add(substring);
            }else {
                set1.add(substring);
            }
        }
        return new ArrayList<>(set2) ;
    }

    public static void main(String[] args) {
//        String str="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        String str="AAAAAAAAAAA";
        List<String> list = findRepeatedDnaSequences(str);
        System.out.println(list);
    }
}
